package algorithms.leecode;

import java.util.*;

public class Au76 {
    public static void main(String[] args) {
        System.err.println(new Au76().minWindow("qwdqawqqddad","qwq"));
    }
    public String minWindow(String s, String t) {

        Map<Character,Integer> map = new HashMap<>();
        char[] cs = t.toCharArray();
        int min = 100000;
        int[] resa = new int[2];
        Deque<Integer> indexDeque = new LinkedList();
        for (int i = 0; i < cs.length; i++) {
            if (map.containsKey(cs[i])) {
                map.put(cs[i],map.get(cs[i]) + 1);
            } else {
                map.put(cs[i],1);
            }

        }
        int start = -1,end = 0;
        for (int i = 0; i < s.length(); i++) {
            char x = s.charAt(i);
            // 如果存在相同key
            if (map.containsKey(x)) {
                if (start == -1) {
                    start = i;
                }
                indexDeque.addFirst(i);
                map.put(x,map.get(x) - 1);
                char ts = '0';
                // 如果当前数据和第一个一样且刚好数量一致
                while (map.get(x) == 0 && check(map,ts)) {
                    if (min > i - start + 1) {
                        resa[0] = start;
                        resa[1] = i + 1;
                        min = i - start + 1;
                    }
                    int first = indexDeque.pollLast();
                    if (!indexDeque.isEmpty()) {
                        start = indexDeque.peekLast();
                    }
                    ts = s.charAt(first);
                    map.put(ts,map.get(ts) + 1);
                }
            }
        }
        return s.substring(resa[0],resa[1]);
    }




    private boolean check( Map<Character,Integer> map,char ts) {
        if (ts != '0' && map.get(ts) > 0) {
            return false;
        }

        for (Integer x : map.values()) {
            if (x > 0) {
                return false;
            }
        }
        return true;
    }
}
